Spectral clustering is a broad class of clustering procedures in which anintractable combinatorial optimization formulation of clustering is "relaxed"into a tractable eigenvector problem, and in which the relaxed solution issubsequently "rounded" into an approximate discrete solution to the originalproblem. In this paper we present a novel margin-based perspective on multiwayspectral clustering. We show that the margin-based perspective illuminates boththe relaxation and rounding aspects of spectral clustering, providing a unifiedanalysis of existing algorithms and guiding the design of new algorithms. Wealso present connections between spectral clustering and several other topicsin statistics, specifically minimum-variance clustering, Procrustes analysisand Gaussian intrinsic autoregression.
展开▼
